package Test;

import java.util.ArrayList;
import java.util.List;

public class test11 {
        List<String> ret = new ArrayList<>();
        StringBuffer path = new StringBuffer();
        public List<String> generateParenthesis(int n) {
            //总的括号对数,已填的左括号数,已填的右括号数
            dfs(n,0,0);
            return ret;
        }
        public void dfs(int n,int l,int r){
            if(r==n) {
                ret.add(path.toString());
                return;
            }
            if(l<n){
                l++;
                path.append('(');
                dfs(n,l,r);
                path.deleteCharAt(path.length()-1);
                l--;
            }
            if(r<l){
                r++;
                path.append(')');
                dfs(n,l,r);
                r--;
                path.deleteCharAt(path.length()-1);
            }
        }

    public static void main(String[] args) {
        test11 t = new test11();
        List<String> strings = t.generateParenthesis(3);
        System.out.println(strings);
    }
}
